\chapter{Problem Analysis}
	\label{chapter:Analysingexistingboardgames}
	Since the rules of a board game are different for each game, it is difficult to give a specific definition of a board game. Typically a board game has its own board design but in some cases a board game shares board design with another game, like Chess and Checkers. Each of these games have a different set of rules which dictate how to play them. A lot of board games use accessories like a die or cards to add more content and complexity to the board game. The more accessories there are in a board game the more rules need to be applied to compensate for the accessories. A game may have several different variations of rule sets. For instance, there are at least two versions of Tic-Tac-Toe: in one, the game ends when the board is full; in another, players have only three pieces each, and may move one piece each round after having placed all three pieces.
	
	At the beginning of this report we want to take a look at a few board games, so we can get a better understanding of what a board game consist of. We do this since we want to design a language that is compatible with most popular games. We will focus on the popular board games; Tic-Tac-Toe, Checkers and Ludo.
	
	%%% This listing makes no sense with the structure of the chapter
	We describe the generalized attributes of a board game in three subsections:
	
	\begin{itemize}
		\item Rules
		\item Accessories
		\item Turn \& Round Order
		\item Conditions
	\end{itemize}
	
	\section{Elements in a Board Game}
		A board game has different elements which define the game. In the following we have compiled an overview of these.
	
		\subsection{Rules}
			The rules are one of the defining aspects of a board game since they determine how the game is played and what limitations there are in the game play. The rules should always be carefully and specifically described to ensure that everbody will understand them.
		\subsection{Accessories}
			There are a lot of different accessories which can come with a board game. Some of the most widely used ones are pieces, dice and cards. 
			
			\subsubsection{Pieces}
				The most important accessories in a board game are the pieces. Pieces can represent players or other items on the board, or even be used as counters to keep track of important numbers. In Chess, the player is represented by a large amount of pieces with different attributes while, in other games like Tic-Tac-Toe, the player only controls pieces with the same attributes.
	
			\subsubsection{Dice}
				Some board games also use one or more dice. Dice can come in a lot of different shapes and have different amounts of sides. The most common type of die has 6 sides which give a total of 6 different numbers or symbols. In many board games these dice are used to determine how far a certain player can travel across the board. In other board games dice are used to determine the outcome of certain scenarios. Dice in general are used to introduce unpredictability into board games.
	
			\subsubsection{Cards}
				In some board games, cards play an important role. Many role playing, casual and quiz board games use them for many different things. A quiz game like ``Trivial Pursuit'' uses cards to display questions which players have to answer. In a role playing game like ``Descent'', cards are used for different items and abilities which a character can possess and obtain. In casual games like ``Monopoly'' a card is used to reward or to punish a player.
				In this context cards can be a very important part of a game.
	
		\subsection{Round \& Turn Order}
			The \textit{Round Order} (RO) determines the order in which players have their turns, whereas the \textit{Turn Order} (TO) describes the what happens in the turn of a player, i.e. each action a player can do when it is his turn. The RO will be repeated until the game ends. When a player is reached by the RO his turn will start. When a player finishes his turn, the next player in the RO gets his turn. The RO and TO are usually very different from game to game.
			
			A turn can be as simple as placing a piece or moving a piece. The RO will usually just repeat until the game ends, but a rule in a board game could interfere with the RO by reversing it or by forcing a player to skip his turn.
	
	
		\subsection{Conditions}
			A condition describes a specific state in the board game. There are many different conditions in most board games. Commonly, board games use the following conditions to determine the start and end of a game. 
	
			\subsubsection{Start Condition}
				The  \texttt{Start condition} (SC) is the first condition of a board game. It defines the initial state of the game, before any turns have been started.
			\subsubsection{Win Condition}
				The \texttt{Win Condition} (WC) specifies when a player has won the game. This does not necessarily mean that the game has ended, but is use to define how a winner is chosen.
			\subsubsection{Lose Condition}
				The \texttt{Lose Condition} (LC) specifies when a player has lost the game. Often, this state is reached if a player is the last one who has not reached the win condition. When a player reaches the lose condition this does not necessarily mean that the game has come to an end.
			\subsubsection{End Condition}
				The \texttt{End Condition} (EC) defines when the game ends. This condition can trigger the lose condition for all players who have not reached the win condition. Note that this condition can be reached even if no player has reached either the win or lose condition. This would be seen as a draw.
	
	\section{Tic-Tac-Toe}
		\label{section:Tic-Tac-Toe}
		
		\begin{figure}[h!t]
			\begin{center}
			\includegraphics[width=0.3\textwidth]{./Analysis/tictactoe.jpg}
			\end{center}
			\caption{The $3 \times 3$ board of Tic-Tac-Toe}
			\label{fig:TTT}
		\end{figure}
		
		This example takes a look at \textit{Tic-Tac-Toe} (TTT), which is a simple board game played by two players. Each player picks either X or O to be his piece. The players then take turns at placing a piece on the board. The player with the X pieces starts. Figure \ref{fig:TTT} shows the board design with the X and O pieces.
	
		\subsection{Elements of Tic-Tac-Toe}
			This section defines the attributes of TTT.
			\subsubsection{Rules}
				The rules of TTT are defined as follows.
				\begin{enumerate}
					\item The board consists of $3 \times 3$ cells.
					\item A player picks a piece type ($X$ or $O$) at the beginning of the game.
					\item The player with the $X$ pieces has the first turn.
					\item A player can only place his own pieces.
					\item A cell is occupied if a player has placed a piece in that cell.
					\item A player can not place a piece in an occupied cell.
					\item A player can only place one piece per turn.
				\end{enumerate}
			\subsubsection{Accessories}	
				The players control pieces with the same attributes. There is a piece type called $X$ which belongs to the first player and a piece type called $O$ which belongs to second player.
	
			\subsubsection{Round \& Turn Order}
				The RO is defined as follows:
				\begin{itemize}
					\item First player's turn.
					\item Second player's turn.
				\end{itemize}
				
				The TO is defined as follows:
				\begin{itemize}
					\item Select a cell
					\item Place a piece
					\item End turn
				\end{itemize}
		
			\subsubsection{Conditions}
				This RO is repeated until the EC is reached.
				\begin{itemize}
					\item The WC is reached if either player 1 or player 2 have three of their pieces a row, column or diagonal.
					\item The EC is reached when the WC is reached, or no valid move can be made. No valid move can be made when all cells contain a piece.
				\end{itemize}
		
	\section{Checkers}
		\label{section:Checkers}
		
		The board game \textit{Checkers} is more complex than TTT since the board is bigger and each player has more pieces. The board is usually composed by $8 \times 8$ cells and the two players have 12 pieces each (see figure \ref{fig:checkers} for the setup).
		
		\begin{figure}[h!]
			\begin{center}
				\includegraphics[width=0.3\textwidth]{./Analysis/checkers.jpg}
			\end{center}
			\caption{Checkers start condition}
			\label{fig:checkers}
		\end{figure}
		
		Only the gray cells on the board -- comprising half the board -- are used. A piece can only move forward one cell at a time diagonally to the right or left. The green arrows in figure \ref{fig:checkersMove} indicate where the grey pieces can move. The piece with the king mark will be explained later.
		
		\begin{figure}[h!]
			\begin{center}
				\includegraphics[width=0.3\textwidth]{./Analysis/checkersMove.jpg}
			\end{center}
			\caption{Checkers movement}
			\label{fig:checkersMove}
		\end{figure}
		
		If an opponent's piece is in the cell diagonally to the player's piece, the player is forced to ``jump'' over the opponent's piece in a diagonal direction -- either left or right toward the opponent's side of the board -- to the next unoccupied grey space. This means that, if player one needs to jump diagonally to the right over the opponent's piece, the piece of player one will be placed forward diagonally to the right from where the opponent's piece was placed. If the piece can jump again, the piece is forced to jump again. An example of this can be seen in figure \ref{fig:checkersJump} where the grey piece is forced to jump three times.
		
		\begin{figure}[h!]
			\begin{center}
				\includegraphics[width=0.3\textwidth]{./Analysis/checkersJump.jpg}
			\end{center}
			\caption{Checkers how pieces can jump}
			\label{fig:checkersJump}
		\end{figure}
		
		If a piece jumps over an opponent's piece, the opponent's piece gets removed from the board.
		It is important to note that only one piece can jump in each round. The player chooses which piece he wants to move in the beginning of each round.
		
		If a piece gets to the other end of the board, the piece changes into a king piece. This can be seen in figure \ref{fig:checkersMove}. Here, the grey piece with a crown is a king. There is no limit to how many king pieces there can be on the board at the same time. A king piece can move diagonally to the left or right like a normal piece. The difference is that a king piece can move backwards as well, as seen in figure \ref{fig:checkersMove}. If a king piece can jump an opponent's piece the, king piece is forced to jump unless another piece can jump over an opponent piece, in which case the player can decide which one he will use.
		
		When a player gets a king piece his round ends. This means that if a piece becomes a king piece, the king piece can not jump over a new piece in the same round.
		
		A player wins the game if an opponent does not have any pieces left, kings included. If a player can not make a valid move, the opposing player wins.
		
		%Checkers is a two player game so here we define the number of players to two like in TTT. We need four different pieces for the two players. There are two set of normal pieces and there are two set of kings. So unlike TTT each player can have two different pieces. As with TTT the board is a grid symmetric grid, but this time of $8 \times 8$ cells. In checkers player one starts and then it is player two. They will keep playing until a player don't have any pieces (kings included) left. After each turn we check if a piece should become a king. Each turn a player can move one piece, but we need to check if there are any pieces that are forced to jump. If a set of piece is forced to jump the player can only chose those pieces. So let's take a look at a round. The first thing we do is checking through all the pieces that belong to the player. We do this to find all the pieces that are forced to jump. If we found any of the player's pieces that are forced to jump, we check if the piece the player wants to move is one of those. If we didn't find any of the player's pieces that are forced to jump, we check if the piece the player wants to move belongs to the player. All we need now is a win condition. This is surprisingly simpler then Tic-Tac-Toe, the only thing we need to check is if one of the two players, don't have any pieces left. Or the other player is unable to move.
		
		\subsection{The rules of Checkers}
			
			Formally, these are the rules of Checkers:
			
			\begin{enumerate}
				\item The board has $8 \times 8$ cells.
				\item Both players pick a piece, either red or grey, at the beginning of the game.
				\item The player with the red pieces has the first turn.
				\begin{enumerate}
					\item Only one piece can be in any one cell at a time.
					\item The pieces are initially set up as in figure \ref{fig:checkers}.
					\item A player can only move one piece in his round.
				\end{enumerate}	
				\item A piece can only move forward\footnote{Toward the opposing player's starting side.} one cell at a time diagonally to the right or diagonally left.
				\begin{enumerate}
					\item If a piece can jump over an opponent's piece, the piece is forced to jump. Also when the piece already has jumped one or more times.
					\item If a player has moved a piece and it can not jump anymore, the player's turn ends.
					\item If a player reaches the opposite side of the board with a piece, that piece becomes a king piece.
					\begin{enumerate}
						\item A king piece can move forwards and backwards one cell at a time, diagonally to the left or right.
						\item If a king piece can jump an opponent's piece the king piece is forced to jump.
					\end{enumerate}
				\end{enumerate}
				\item If a player has more than one piece, including the king piece, which can jump, the player can choose which of the pieces he jumps with.
			\end{enumerate}
			
		\subsection{Accessories}
			There are 12 pieces with the same attributes for each player. A piece can obtain a different attribute by becoming a king piece.
			\begin{itemize}
				\item The pieces
				\begin{itemize}
					\item Can move diagonally to the left and right but only forward.
				\end{itemize}
				\item The king piece
				\begin{itemize}
					\item Can move diagonally to the left and right both forward and backward.
				\end{itemize}
			\end{itemize}
		\subsection{Round \& Turn Order}
			The RO in this game is linear and has no variation.
			\begin{itemize}
				\item The player with the grey piece takes his turn.
				\item The player with the red piece takes his turn.
			\end{itemize}
			
			The TO is more complex than the one of TTT since the players have more possibilities.
		
			\begin{itemize}
				\item If one or more of the player's pieces can jump.
				\begin{itemize}
					\item Chosse a piece to jump with.
					\item Jump across the opponents piece.
				\end{itemize}
				\item If none of the player's pieces can jump.
				\begin{itemize}
					\item Choose a piece and move it into an empty cell.
				\end{itemize}
			\end{itemize}
		 
		\subsection{Conditions}
			A player reaches the WC when all of his opponent's pieces have been removed from the board.
			
			The EC is reached when the players agree on a draw or when a player has reached the WC.
		
	\section{Ludo}
		\label{section:Ludo}
		
		\begin{figure}[h!]
			\begin{center}
				\includegraphics[width=0.7\textwidth]{./Analysis/ludo.png}
			\end{center}
			\caption{Ludo}
			\label{fig:ludo}
		\end{figure}
		
		Ludo is a board game which can be played by at least two players, up to a maximum of four. Each player has four pieces at all times. The board design, see figure \ref{fig:ludo}, indicates that each player has pieces in a specific color. The starting area of each player is the big colored square. Each piece is placed in one of the four white circles. To decide which player has the first turn, each player rolls a die. The player with the highest number starts. If two or more players roll the same highest number, they reroll. 
		
		The players then take turns rolling the die. If a player is able to roll a six, the player can move one of the pieces onto the globe with the same color as his starting area and end his turn without rolling again. There can only be one piece on this globe at any given time and a piece of that particular color can not be removed from the game while standing on his globe. If a player does not have a piece outside his starting area, he can roll a total of three times. If he does not get a six in any of the rolls, his turn ends. A player is only allowed to roll the die once while he has pieces outside his starting area. 
		
		While having a piece outside his starting area, a player can move one piece a number of cells equal to the number of eyes on the die he just rolled. If the player gets a six, the player can choose to move a piece out of his starting area, or move a piece that is already outside.
		If the cell he wants to move to is occupied by another piece of an opposing player, the opposing player's piece is moved back to its starting area. If a piece reaches a cell containing a star, the piece moves to the next star on its path and ends the turn.
		
		While a piece stays on a globe, it is safe from being sent home. There is one exception to that rule, however. If player one's piece is on the globe marked with player two's color, and player two rolls a six and moves another piece into play, player one's piece gets sent home.
		
		When a piece has moved all the way around the board and arrived at the last star, before beginning a new round, instead of continuing to a new round the piece moves in to the cells marked with that player's color.
		
		The goal of the game is for a player to get all his pieces into his final four cells. The first player to succeed has won. But the players can choose to keep playing to get ranked second, third and fourth.
		%The board design in Ludo is not a grid, but rather a bended track. Thus we must be able to find an easy way of describing such track. This could be by describing it as a directed graph, where each cell points to the next.
		
		\subsection{The Rules of Ludo}
			
			Formally, these are the rules of Ludo:
			
			\begin{enumerate}
				\item The board has a track of 54 cells.
				\begin{enumerate}
					\item Each player has four cells where his pieces are initially placed: the home area.
				\end{enumerate}
				\item Each player starts at a different area. The last four cells of the player's color are the finish area.
				\begin{enumerate}
					\item A roll is performed by every player to determine the 
					\begin{enumerate}
						\item The player with the highest number he gets the first turn. After the first turn, players continue to take turns in a clockwise manner.
						\item If two or more players roll the same number, they reroll.
					\end{enumerate}
				\end{enumerate}
				\item Only one piece can be in any cell at a time.
				\item A player can only move one piece in his turn.
				\item A piece can only move clockwise.
				\item If a player piece ends up in the same cell as an opponent's piece, the opponent's piece is moved back to his home area.
				\item A player can not send his own pieces back to the home area.
				\item If a player can make one or more valid moves he has to perform one.
				\item When a piece reaches the final four cells they have to enter them with using the exact number of die eyes required.
			\end{enumerate}
			
		\subsection{Accessories}
			Each player has four pieces of their own color, and all players share a six sided die.
			\begin{itemize}
				\item The pieces
				\begin{itemize}
					\item The pieces can only move in a clockwise direction and only up to six cells in one turn. The only exception is the star cells.
					\item All pieces of a player have the same attributes until one of the pieces reaches the last four final cells.
					\begin{itemize}
						\item The pieces that in the 4 final cells have special attributes.
						\item The pieces cannot exit the final cells and turn around each time it reaches the last or the first cell.
						\item A player continues to play until all his pieces are lined up in the final cells.
						\item A player cannot move to a cell occupied with his own piece.
						\item A player needs to roll the exact number of cells his piece needs to travel, in order for the move to be valid.
					\end{itemize}
				\end{itemize}
			\end{itemize}
		
		\subsection{Round \& Turn Order}
			The RO in this game is linear and has no variation.
			\begin{itemize}
				\item Player 1
				\item Player 2
				\item Player 3, if he exists
				\item Player 4, if he exists
			\end{itemize}
			The TO is much more complex than that of TTT since the players have more possibilities.
			\begin{itemize}
				\item If no pieces outside starting area
				\begin{itemize}
					\item Roll die up to three times.
					\item If a six appears, move piece from home to globe and end turn.
				\end{itemize}
				\item If one or more pieces outside starting area
				\begin{itemize}
					\item Roll the die.
					\item Choose a piece and move the piece the number of cells which the die shows.
					\item If a six is rolled, the player may choose to move a piece from home onto the globe instead of moving a piece.
				\end{itemize}
			\end{itemize}
		 
		 
		\subsection{Conditions}
			A player reaches the WC if all his pieces are within the final four cells.
			
			The EC is reached when all but one player have won.
		
		%The track contains 54 cells, not including the start zones and the player reserved cells. We need a way to describe how these 54 cells are laid out. It will not be easy to describe it as a grid, because there are a lot of cells not in use.
		
		%But we not only need to describe a plane board like in TTT, Ludo need special cells on the board. The star, the globus and the home cell. So we need to define special cells with special properties. A star cell would have the property to move a player to the next star cell. A globe would have the property to provide protection against other player's pieces. 
		
		%We also take a look at the small sample of rules in Ludo. In Ludo a players rolls a six sided die, and depending on the die he takes action. If a player does not have any pieces out of the start area, the player will need a six to get a piece out of the starting area and on to the globe marked with the same color as the players pieces. Once a player has one piece out of the starting area and rolls a die, the player can move the amount of the cells that corresponds to the number of eyes on the die or in case of a six, choose to get another pieces onto the board.
